package slidingwindow

import "container/list"

func GetMonotonousStack(nums []int) [][]int {
	// 位置信息 如：[0:[-1, 3]] nums[0] 位置左边比他小的值没有， 右边比他小的值的index为3
	posInfo := make([][]int, len(nums))
	for i:=0; i<len(posInfo); i++ {
		posInfo[i] = make([]int, 2)
	}

	monotStack := list.New()

	for i, num := range nums {
		// 长度大于0的时候，进入时如果最后一个值小于数组列表的最后一个，需要弹出之前的内容并且记录
		for monotStack.Len() > 0 && nums[monotStack.Back().Value.([]int)[0]] > num {
			popIs := monotStack.Remove(monotStack.Back()).([]int)
			leftLessIndex := -1
			if monotStack.Len() > 0 {
				beforeIs := monotStack.Back().Value.([]int)
				leftLessIndex = beforeIs[len(beforeIs)-1]
			}
			for _, v := range popIs {
				posInfo[v][0] = leftLessIndex
				posInfo[v][1] = i
			}
		}
		if monotStack.Len() > 0 && nums[monotStack.Back().Value.([]int)[0]] == num {
			popIs := monotStack.Remove(monotStack.Back()).([]int)
			monotStack.PushBack(append(popIs, i))
		} else {
			monotStack.PushBack([]int{i})
		}
	}
	for monotStack.Len() > 0 {
		curArr := monotStack.Remove(monotStack.Back()).([]int)
		for _, v := range curArr {
			leftLessIndex := -1
			if monotStack.Len() > 0 {
				beforeIs := monotStack.Back().Value.([]int)
				leftLessIndex = beforeIs[len(beforeIs)-1]
			}
			posInfo[v][0] = leftLessIndex
			posInfo[v][1] = -1
		}
	}
	return posInfo
}
